其他
2023年，量子算法的应用清单（上篇）
光子盒研究院
量子计算机的预期应用横跨科学和工业领域，从量子化学和多体物理学到优化、金融和机械学习。在这些领域提出的量子解决方案通常将多个量子算法基元组合成一个整体量子算法，然后必须结合量子纠错和容错方法，才能在量子硬件上正确实施。因此，很难评估特定应用能从量子计算中获益多少，因为各种方法往往对底层基元的复杂技术细节及其复杂性非常敏感。
在近期公布在arXiv上的一篇文章中，美国亚马逊、哈佛大学的科学家们联合英国帝国理工学院、德国和丹麦的科学家们对量子算法及其底层算法基元的几个潜在应用领域进行了调查，并仔细考虑了技术上的注意事项和微妙之处。
科学家们以“端到端”的方式概述了每个领域所面临的挑战和机遇，明确定义了所要解决的问题以及输入-输出模型，实例化了所有的“谕令”，并阐明了所有隐藏的成本。最后，团队还将量子解决方案与最先进的经典方法和复杂性理论限制进行比较，以评估可能的量子提速。
/目·录/
一、当前量子算法的机遇和挑战
二、量子算法模拟凝聚态物理学
2.1. 费米-赫巴德模型
2.2. 萨奇德夫-叶-基塔耶夫(SYK)模型
2.3. 自旋模型
三、量子算法计算化学体系
3.1. 电子结构问题
3.2. 振动结构问题(Vibrational structure problem)
四、量子算法解决核物理、粒子物理问题
4.1. 模拟量子场论
4.2. 核结构问题
1985年，多伊奇给出了第一个量子算法：一个简单的程序，只需一个黑盒查询，就能完成一个经典上需要两个查询的任务。在接下来的十年中，人们发现了更大的黑箱分离算法，如Deutsch-Jozsa、Bernstein-Vazirani和Simon算法。
1994 年，第一个真正意义上的端到端查询算法诞生了：肖尔算法用于因式分解整数和计算离散对数，为密码学带来了广泛的影响。这一突破表明，量子计算机不仅可以加快解决设计好的黑箱问题，而且至少在理论上可以更快地解决现实世界中的重要问题。肖尔算法的发现使量子算法领域从一个相对小众的课题变成了一个重要的研究领域。
在肖尔的开创性发现之后的三十年里，量子算法领域取得了长足的发展。例如，我们对黑箱问题的量子查询复杂度上下限的了解（通常是通过复杂的、非构造性的数学论证推导出来的）得到了极大的扩展。此外，许多额外的量子算法和子程序（例如，量子模拟和线耳代数的基元）已经被发现、优化，并被多次推广。
与此同时，硬件和容错量子计算理论的进步已经到了可以想象的地步，这些算法（其中一些）可能很快就能在足够大的规模上实现，从而超越经典算法。
然而，现实世界应用中可用的量子提速幅度往往难以评估，而且可能会被底层量子算法基元中的技术注意事项、假设和限制所掩盖。尽管肖尔的因式分解算法是最古老的算法之一，但可以说它仍然是针对现实世界中具有重大意义的问题，以最少的注意事项实现大幅量子提速的最简洁的例子。这项调查旨在阐明端到端量子计算应用的真正资源需求，从而帮助确定容错量子计算机最可能的应用。
要真正了解量子算法的潜在优势，就必须以“端到端”的方式考虑其资源需求。文中所说的“端到端”是指解决用户感兴趣的整个问题的成本，而不仅仅是运行作为完整解决方案子程序的特定量子电路的成本。这意味着，我们必须考虑所有量子和经典开销：跟踪经典预计算和后处理、明确实例化量子算子和数据访问结构，以及理想情况下计算所有量子子程序的常数因子（包括与容错协议和量子纠错相关的开销）。
不过，这项任务对于复杂的量子算法来说是一项艰巨的任务，因此文献中只有少数量子算法实现了这项任务。除了研究“端到端”量子复杂性，还需要将量子结果与同一问题的最新经典解决方案以及已知的复杂性理论限制进行比较。
此次，研究团队表示，“我们总结了一些领先的量子应用提案（我们指的是应用于定义明确的实际问题的量子算法）的端到端复杂性。这些应用的复杂性是从其底层基元的复杂性中推导出来的，我们对这些基元进行了详细评述。”
调查报告的模块化结构有助于人们从高层次理解在设计和编译量子算法时所作的各种选择带来的成本和权衡，以及识别特定应用的瓶颈。在技术方面，本调查报告并不试图推进技术发展，而是旨在收集、综合和概括文献中的关键成果。“我们考虑的是量子电路模型中的算法，这可以说是量子计算研究得最透彻的模型，并使所提出的复杂性与硬件无关。我们通常假定，由于所有已知量子硬件模式固有的不可避免的缺陷，某种形式的量子纠错是必要的。因此，我们通常将量子算法的非克利福德成本视为主要成本，与领先的量子容错方案保持一致。”
“在整个调查过程中，我们力求详尽，但不会面面俱到；我们的目的只是提供有代表性的参考文献，而不是提供一份完整的清单。一般来说，我们会尽量解释渐近复杂性声明是如何从其底层基元中产生的，但技术结果通常没有明确的推导或证明，读者可参阅所引用的参考文献。此外，我们经常引用文献中的资源估计值，但并不包括为达到所报告的常数因子而需要对底层基元进行的所有特定应用优化。我们调查了许多量子应用、基本原理和容错方案，但忽略其他方法并不表示它们不重要。此外，这项工作的范围还排除了一些重要课题，例如：量子传感或通信、基于测量的量子计算、绝热量子计算和量子退火、模拟量子模拟器、量子启发方法和张量网络算法。”
本次调查的一个重要结论是，目前的文献普遍缺乏对具体量子应用的端到端分析。因此，在本调查的几个部分中，并没有实现完全令人满意的端到端分析。量子算法研究通常从算法基元出发，确定具有最大量子加速度的计算任务，但这些任务可能与用户最相关的任务并不一致。另一方面，潜在用户本身可能还不清楚他们将如何使用新功能来推进其高层次目标。
然而，我们发现自己正处于量子计算发展史上的一个重要阶段，我们应该填补这些细节并采用端到端“透镜”。随着更多端到端应用的出现，以及小型容错量子计算机的问世，“我们预计量子计算将继续发展：本调查报告为2023年的发展状况提供了一个缩影” 。虽然改进的量子算法以及量子纠错和容错方法很可能会被发现，但经典计算机的规模和速度仍在继续增长，经典算法也在不断完善和发展，从而推动端到端量子提速目标的实现。
凝聚态物理学构建并研究旨在捕捉材料系统普遍物理特性的简化模型的行为。感兴趣的现象包括：磁性、相变、超导性、拓扑相，以及封闭系统中热化和多体局部化的相互作用。
虽然许多开创性模型（如一维和二维经典伊辛模型）可以在某些限制条件下进行分析研究，但一些看似无害的模型却被证明极其难以解决。这导致一些模型（如费米-赫巴德模型）成为经典数值方法的试验场。虽然近几十年来通过数值模拟理解这些模型的物理过程取得了重大进展，但对于许多模型和参数体系来说，这仍然是一个具有挑战性的问题。
正如费曼所观察到的，量子计算机在模拟凝聚态物理中研究的简单汉密尔顿时，比经典计算机具有天然的优势。虽然费曼的提议更侧重于模拟仿真，但凝聚态系统的数字量子仿真已发展成为一个主要研究方向。在本节中，我们将重点讨论那些端到端复杂性已在文献中得到充分研究的模型：费米-赫巴德模型、萨奇德夫-叶-基塔耶夫(SYK)模型和自旋模型。
1、费米-赫巴德模型
费米-赫巴德模型最初是作为物质中电子的简化模型而提出的，与紧密结合模型密切相关。它表现出广泛的行为，包括金属、绝缘和反铁磁相。该模型最近被用于研究高温超导；二维费米-赫巴德模型具有复杂的相图，似乎再现了铜氧化物高温超导体相图的普遍特征（而非化学特异性特征）。
目前还不知道一般的解析解（除了一维链或特定参数区--最近的讨论），这促使人们使用数值方法来理解费米-赫巴德模型的物理原理。最近，人们对了解该模型的非平衡特性越来越感兴趣，例如它在淬火后的行为。
根据目前的估计，费米-赫巴德模型的量子模拟所需的资源要比模拟分子或解决优化问题少得多。因此，费米-赫巴德模型有望成为量子优势早期演示的候选模型。
费米-赫巴德模型的主导资源成本/复杂性可以总结如下：
1）将问题映射到量子比特：费米-赫巴德模型的仿真最自然地是在二次量化表示中进行的，因为所关注的体系通常接近半填充（例如分子仿真）。费米子和量子比特之间通常使用乔丹–维格纳变换（其他映射是否能在容错设置中提供具体优势尚未确定）。对于L×L晶格，我们需要M = 2L^2 个量子比特来使用乔丹–维格纳变换模拟自旋费米-赫巴德模型。
2）访问哈密顿：模拟费米-赫巴德模型的量子算法需要访问哈密顿。这通常由块编码或哈密顿模拟提供，费米-赫巴德结构降低了这些子程序的成本。
现在，针对费米-赫巴德模型的静态和动态特性，已经有许多算法进行了容错资源估算。下表列出了模拟二维10 × 10自旋费米-赫巴德模型的近似资源估算值；表中列出了运行算法所需的逻辑量子比特和门的数量，这些可以通过容错量子计算的方法转换成物理资源估算值。
一般来说，制备费米-赫巴德模型的基态是一个众所周知的难题，即使对量子计算机来说也是如此。对于磁场依赖于场址的费米-赫巴德模型和磁场依赖于场址的t → tij的费米-赫巴德模型，这项任务已被证明是QMA难题。虽然经典费米-赫巴德模型的复杂度等级尚不清楚，但在通过量子相位估计或特征态滤波方法制备基态时，有必要制备一个重叠度随系统大小衰减不小于多项式的初始态；否则，总体复杂度将是超多项式的。虽然对小系统规模的数值模拟显示了令人鼓舞的结果，但这一特性是否适用于足够大的系统规模、从而能够外推到热力学极限，仍然是一个悬而未决的问题。
同样重要的是要注意到，在一系列有限系统尺寸下计算得出的测量属性外推至热力学极限，已被观察到在经典方法中造成了相当大比例的不确定性和误差，并且也会影响量子模拟。
最后，有必要大量重复模拟。为了绘制和计算相图的性质或提取淬火后的相位，我们可能需要测量大量的观测值。在某些情况下，可能需要为每个观测值重新准备初始状态。
费米-赫巴德模型一直是开发和测试静态和动态特性经典数值方法的沃土。计算相图的最先进方法包括：量子蒙特卡罗方法（行列式QMC、图解MC、辅助场QMC、扩散MC）、密度矩阵重正化群(DMRG)、耦合簇方法、杂质方法（动态均值场理论、密度矩阵嵌入理论）等。这些方法通常都有一个近似参数（如耦合簇中的激发度或DMRG中的键维），它会影响算法的缩放和模拟的精度。
费米-赫巴德模型的现代数值研究通常使用多种模拟方法进行交叉验证；对于经典方法来说，费米-赫巴德模型的动力学模拟似乎更具挑战性。
计算费米-赫巴德模型的静态特性（如基态能量）的量子算法的速度提升很难确定。一般来说，我们知道与之密切相关的模型都是QMA-hard，因此对于经典计算机和量子计算机来说都应该是指数级的困难。假设初始态与目标特征态有重叠，且衰减速度不超过多项式，那么量子相位估计可以用来高效测量特征能，并投射到所需的特征态。
使用量子算法模拟费米-哈密顿的动力学需要多项式资源，几乎以M和τ的线性比例扩展。虽然这支持了指数量子加速的结论，但我们注意到经典方法可能会继续改进，并应用于越来越大的系统规模。通过使用精心设计的相互作用（例如，明显偏离正方形晶格），可以证明在平面图上模拟费米-赫巴德模型的动力学是一个BQP-complete问题，因此预计在最坏的情况下，经典计算机也很难做到。
在NISQ硬件上模拟费米-赫巴德模型的建议（和实验演示）有很多。基态计算可使用变分量子求解器(VQE)，实验演示已在大小为1×8和2×4的晶格上使用16个超导量子比特进行，结果与理论预期基本一致。也可以使用哈密顿模拟（通常是特罗特方法）来模拟动力学，并已在16个超导量子比特的8×1晶格上进行了演示。
费米-赫巴德模型的哈密顿简单，非常适合在模拟量子模拟器中实现，包括光学晶格中的超冷原子、捕获离子和中性原子阵列。有观点认为，某些局部观测值对模拟中的误差具有鲁棒性，这使得模拟仿真在模拟动力学方面已经超越了经典方法。
事实上，费米-赫巴德模型提供了一个长期存在的、与物理相关的计算挑战。计算基态能量所需的低门数和适量的逻辑量子比特可以使量子算法在具有挑战性的情况下与领先的经典方法竞争；要确定这些计算的初始状态准备成本，还需要进一步的研究。对于研究较少的模拟费米-赫巴德模型动力学的任务，量子算法目前比已知的经典算法有指数级的提速。尽管如此，由于费米-赫巴德哈密顿方程非常简单、可以在许多受控物理系统中实现，未来的容错量子计算机还必须与模拟量子模拟器竞争。
2、SYK模型
萨奇德夫-叶-基塔埃夫(SYK)模型是一个简化的量子黑洞模型，它具有强耦合性和“最大混沌性”，但仍然是可解的。这种非凡的、迄今为止独一无二的特性组合引发了围绕SYK的大量研究活动。通过与黑洞和量子引力的联系，它在高能物理中得到了应用；作为量子混沌和扰乱的模型，它在凝聚态物理中得到了应用，从而揭示了强耦合金属中的物质相。
虽然SYK模型的许多有趣特性可以在某些限制条件下进行分析计算，但并非所有特性都符合条件，而且模型在这些限制条件之外的行为仍然存在问题：这些问题有可能通过量子计算机以数值方式加以解决。
SYK模型的主导资源成本/复杂性可以表示为：
1）将问题映射到量子比特：为了在量子计算机上模拟SYK模型，根据乔丹-维格纳表示法，马约拉纳算子由一系列保利算子表示。因此，N个马约拉纳上的哈密顿方程HSYK变成了N/2量子比特上多量子比特泡利算子的线性组合。
2）状态准备：为了解决估算tr(ρO)的问题，我们必须能够预处理(N/2)-qubit状态ρ。如果ρ是反向温度β下的热态，那么将使用吉布斯取样算法来制备该状态。由于SYK的混沌特性以及系统在自然界中会迅速热化的事实，我们预计蒙特卡罗式吉布斯采样器具有良好的poly(N)门复杂度，但具体性能尚不清楚。
3）时间演化：计算还需要模拟HSYK的时间演化。这可能是因为O是一个时间演化算子，也可能是因为状态ρ对应于一个时间演化状态，或者仅仅是上文提到的QPE或吉布斯采样的一个子程序。
4）测量观测值：最后，如果能够准备ρ的净化，并假设O是单元的（如果不是，则可以分解为单元的总和，并分别计算每个成分），则可以通过重叠估计来估计精度为ϵ的期望值tr(ρO)，对准备ρ的例程和应用O的例程的调用代价为O(1/ϵ)。
现有的资源估算只关注模拟SYK模型的动态，但所提出的经典挑战性问题涉及静态属性：如状态密度和热状态属性。要以端到端方式探测这些静态特性，除了能够实现eiHt之外，还可能需要制备热态、基态或其他类型的低能态。准备这些状态的成本尚不清楚，也很难进行分析评估。另一个需要注意的问题是，上面引用的门计数并没有考虑读出精确度为ϵ的可观测物的O(1/ϵ缩放，也没有考虑推断SYK物理学所需的不同HSYK实例的任何重复。
如上所述，SYK模型之所以吸引人，其中一个原因是它的许多性质都可以在一定限度内通过分析计算出来。在量子计算机上进行数值计算所需的其他性质则需要扩展性较差的经典方法。由于希尔伯特空间的指数增长，对超过大约50个费米子组成的系统进行精确对角将非常具有挑战性。
哈密顿模拟的运行时间为 poly(N)，与精确对角化相比，速度呈指数级增长，是经典模拟SYK相关问题的常用方法。然而，哈密尔顿模拟并不能单独解决与精确对角化相同的端到端问题；指数加速的持续性需要确定特定的有趣属性，在这些属性中，相关的初始状态也可以在poly(N)时间内准备好，而这一点目前还不太清楚。
已经有人提出在多个不同的实验平台上实现SYK模型；不过，即使这些演示能够实现，我们也不指望这种方法在没有量子纠错的情况下能够扩展。
在量子计算机上模拟SYK模型的时间演化，门控成本相对较低，这是因为该模型可以直接映射到量子位哈密顿。与此同时，由于SYK模型具有混沌和强耦合的性质，因此很难在经典计算机上模拟SYK模型。然而，要了解整个端到端管道还需要进一步的工作。目前尚未确定在量子计算机上计算哪些特性最有价值，以及这些特性的成本有多高：计算这些特性所需的时间可能远远超过在SYK模型的单个实例上运行一次时间演化，因此总体成本可能远远大于文献中最初的门数。
3、自旋模型
经典和量子自旋系统是各种物理现象的原型模型，包括：磁性、神经元活动、材料和分子的简化模型以及网络。研究自旋哈密顿的特性还能为量子信息科学提供有用的见解。
许多科学和工业问题都可以映射到寻找经典或量子自旋模型的基态或热态上，例如解决组合优化问题、在机器学习中训练基于能量的模型，以及模拟量子化学的低能模型。模拟量子自旋模型的动力学主要涉及量子形成科学、凝聚态物理或化学，例如解释核磁共振或相关光谱学实验。
由于自旋-1/2系统与量子比特之间的自然映射，以及通常存在的相互作用的局域性，使用量子算法模拟简单自旋模型所需的资源可能远低于量子化学或密码学等领域的问题。
虽然我们的讨论将集中在设计用于在容错量子计算机上运行的量子算法上，但自旋模型的简单哈密尔顿原理可以在许多物理系统中自然实现。因此，人们开始使用模拟模拟器，如捕获离子阵列或中性原子阵列，来模拟有趣的自旋模型的静态和动态特性。
对于由N个自旋-1/2粒子组成的系统，我们需要N个量子比特来表示系统的状态；对于N个自旋-S粒子，可以用不同的方法将问题映射到量子比特。在模拟自旋系统的时间演化时，最有效的算法是利用哈密顿中相互作用的局部性以及由此产生的换向结构。对于具有近邻几何位置性的D维晶格上的2局域自旋-1/2系统，已知有几乎最优门复杂度的算法来执行时间演化。
已有的文献中报道了许多用于模拟自旋系统动力学或通过量子相位估算寻找其基态的容错资源估算。在这类计算中，有必要优化所使用算法基元的常数因子贡献。
在容错量子计算机上，必须使用更多的T门和克利福德门合成任意角度旋转门。如果一组并行旋转门具有相同的角度，就可以减少合成T门的数量。这种技术可用于模拟物理自旋系统的容错编译算法，因为物理自旋系统通常具有平移不变性等特征。
2局域经典自旋模型和量子自旋模型的基态问题的决策形式分别是NP-完全和QMA-完全。因此，我们并不指望量子算法能在一般情况下为这些问题提供有效的解决方案。尽管如此，鉴于经典启发式算法在这些问题上的成功，人们可能希望从量子启发式算法（如蒙特卡罗式吉布斯采样算法）中观察到类似的好处。
相比之下，模拟自旋模型的动力学是一个BQP-complete(BQP-complete)问题，很可能是未来容错量子计算机上可以进行的最简单的超经典计算之一。虽然这样的计算会带来极大的科学兴趣，为量子信息和多体物理学提供新的见解，但目前还不清楚大型系统的动力学模拟是否会对工业相关应用产生直接影响。
量子自旋模型的精确经典模拟在系统规模上是指数级昂贵的。因此，使用最大的经典超级计算机，考虑到时间演化足以让信息在整个系统中传播（如利布-罗宾逊约束）的精确模拟只能局限在50个自旋左右。
研究量子自旋系统的近似经典算法包括张量网络方法和量子蒙特卡罗方法。这些方法为计算低维度物理自旋系统的基态、特别是具有局部相互作用的自旋系统的基态提供了经验上的精确结果。例如，局部间隙一维哈密顿的基态具有面积律纠缠，因此可以用矩阵乘积态有效地表示。在二维中也可以使用类似的方法，如投影纠缠对态(PEPS)。
相比之下，这些方法在模拟量子自旋动力学时的准确性较低。在这些系统中，纠缠熵随时间呈线性增长，这导致以固定精度为目标的张量网络方法的成本随时间呈指数增长。
许多物理系统都会受到与其环境强烈相互作用的影响，这限制了它们的相干时间。在这种情况下，通常可以通过模拟较少数量的自旋（例如≤30）、并通过物理启发式方法考虑与环境的相互作用，来重现系统的行为。这种模拟（可通过开源软件库访问）可用于分析核磁共振和μ介子光谱实验。
与经典近似方法（如张量网络或量子蒙特卡罗）相比，计算量子自旋哈密顿的基态的速度提升目前是一个悬而未决的研究问题。大幅提速似乎需要为量子算法提供良好的初始态，而同时又能高效地解决经典问题。
使用所有已知的经典方法模拟量子自旋动力学似乎都要付出指数级的代价。因此，哈密顿模拟的量子算法将为这项任务提供指数级的加速。这很可能为量子信息和多体物理学提供启示：例如，这种系统可以研究量子系统中热化和多体定位之间的竞争和相互作用。
量子自旋模型通常被用作NISQ算法的基准系统，例如寻找基态、模拟动力学或探测热化。自旋模型的哈密顿也可以在各种物理系统中自然实现，包括捕获离子或中性原子。例如，最近在中性原子系统中进行的实验研究了O(200)个自旋的动力学，这超出了通过矩阵乘积状态方法进行经典模拟的能力；模拟模拟器已经成为提供新科学见解的重要工具，它们为未来模拟自旋系统的容错方法的性能设定了很高的标准。
模拟自旋系统的行为可以说是量子计算机最自然的任务之一，而使用所有已知的经典方法，模拟成本都是指数级的。这种模拟可以为量子信息和多体物理方面的问题提供重要的见解，还可以作为凝聚态物理和化学中更复杂系统的模型。
模拟自旋系统的量子算法的容错资源估算值是已知超经典任务中最低的。尽管如此，模拟量子模拟器已经能够原生模拟数百个自旋的动力学。为了超越这些能力，数字方法可能需要考虑更复杂的观测指标，或以误差修正无法实现的精度为目标。
此外，对于化学或凝聚态物理等相关领域的许多科学系统来说，与环境的退相干性相互作用往往限制了所需的模拟规模。确定需要精确模拟大型自旋模型动力学的应用，将提高量子算法在这一领域的影响力和适用性。
计算化学试图利用量子力学规则来预测原子、分子和材料的物理性质和行为。尽管用精确的经典方法来完成这项任务显然要付出指数级的代价，但在过去的一个世纪里，科学家们通过日益复杂的近似方法取得了令人难以置信的进展。
因此，计算化学现在已成为化学实验分析、药物研发以及催化剂和电池材料优化的核心部分。其中，最广泛的两种计算是化学体系的电子结构和振动结构计算。鉴于这些问题本身具有量子力学性质，因此人们提出了许多用于计算化学的量子算法。
1、电子结构问题
我们寻找用于描述分子或物质系统中电子的哈密顿的能量特征状态（或热态）。除了由原子核（通常假定原子核位置固定、经典）和任何外部应用场产生的场之外，电子之间也会相互作用。
在有限尺寸系统的模拟中，“分子”和“材料”之间没有明显的区别：材料可被视为扩展分子，通常具有重复的基本原子结构。在材料方面，我们还关注通过在一系列系统尺寸下重复模拟，将有限尺寸特性推断到热力学极限。这样就可以测量相图等热力学性质。对于分子系统，我们感兴趣的是测量微观特性，如激发能、反应速率、偶极矩或核力。
我们还可以考虑电子结构哈密顿下的时间演化；这在经典和量子环境中都是一个研究较少的问题，可能是因为经典模拟的成本较高。
在动力学模拟中，我们可以考虑系统如何对诸如由超快激光脉冲或粒子散射相互作用等引起的每一次扰动做出响应。这其中，主要的资源成本/复杂性在于：
1）将问题映射到量子比特：通过投影到自旋轨道的基础上，对电子位置进行离散化。离散化误差通常以1/N的形式衰减，其中N是所使用的自旋轨道数，并受限于电荷凝聚处库仑相互作用奇异性的分辨率。
2）访问哈密顿：电子结构问题的量子算法需要访问哈密顿，这通常由块编码或哈密顿模拟提供。对于某些方法，可能需要相干地计算哈密顿系数（分子积分）或矩阵元素，或从量子存储器中加载它们。由于这种访问往往是量子算法成本的主要部分，因此人们花费了大量精力研究如何对电子结构哈密顿进行因式分解，以减少相干访问所需的资源。一些数据加载例程可以用门计数换取额外的辅助量子比特，从而获得比存储系统波函数所需更多的逻辑量子比特数。
3）状态准备：在量子计算机上解决电子结构问题可以简化为制备所需的状态并测量观测值。需要制备的状态通常是能量特征态、热态或时间演化态。
4）测量观测值：在容错计算中，最好通过类似相位估计的方法来测量观测值，而不是直接测量平均值，因为前者在渐近上更有效率，而且可以通过重复和多数表决来抵御逻辑错误。目前已经开发出了利用重叠估计可视为振幅估计的特例）或基于量子梯度估计算法的方法来实现这一目标的测量方案。
上表列出了大量用于进行相位估算以了解分子或材料系统基态能量的资源估算。这些资源估算使用的是容错量子计算部分所述的编译方法。可以注意到，有一个软件包提供了计算电子结构问题量子相位估算的非克里福成本的功能，目前还没有任何成果能够为解决完整的端到端应用提供资源估算。
对化学动力学模拟所需的容错资源的研究相对较少。最近的研究计算了计算带电粒子在介质中运动的能量损失所需的资源，这与核聚变实验有关。研究确定了端到端资源估算，包括初始状态准备、观测值测量和在一定参数范围内重复计算的成本。
现有的资源估算通常只考虑相位估算的一次运行，并假定我们可以获得所需的能量特征状态。随着我们的规模达到热力学极限，这个问题对于材料系统来说可能会变得更加紧迫。一般来说，我们知道寻找电子结构哈密顿的基态问题是QMA难的，但这些复杂性理论声明是否能为物理上现实的哈密顿提供直观的解释，目前还不得而知。
要精确解析系统，必须使用大的基集（分解误差以1/N的形式衰减，其中N是所考虑的自旋轨道数）。在实践中，人们通常会使用越来越精确的基集重复计算，然后推演到连续极限。迄今为止，大多数量子资源估算都考虑了最小允许尺寸的基集，因此低估了获得足够精确的结果所需的资源。
通常解决电子结构问题的端到端应用可能需要数十（结构确定）到数百万（分子动力学）次的能量评估：次评估都有不同的哈密顿参数，可能需要准备一个新的待测态。在为每种构型制备不同状态并测量其能量时，这将带来巨大的开销，尽管替代方法可能提供更有利的缩放。
电子结构哈密顿精确对角化的成本与电子数和基集大小成指数关系。因此，解决电子结构问题的经典方法通常采用一系列近似值，这些近似值可将复杂度降低到近似参数的多项式，但会引入对精确基态的（潜在的）不可控偏差，从而导致能量估计值和/或其他观测值的期望值出现偏差。这些方法包括哈特里-福克(Hartree-Fock)方法、密度泛函理论、扰动理论、构型相互作用方法、耦合簇方法、量子蒙特卡罗技术和张量网络方法。
最便宜的方法可以应用于数千个轨道，但对于强相关系统来说，可能在质量上不准确；最昂贵的方法对强相关系统更有效，但其较高的计算成本限制了它们在大约100个自旋轨道上的适用性。
由于材料系统具有扩展性，因此最常用密度泛函理论(DFT)可以作为研究对象。密度泛函理论可应用于具有数千个电子和原子的系统，但在强相关系统中会导致失控的能量偏差。量子蒙特卡罗和张量网络方法已成功应用于物质系统的原型模型，对于更现实的模型也越来越实用。
解决电子结构问题是研究最广泛、最受推崇的NISQ应用之一。主要的 NISQ 方法是变分量子求解器(VQE)。目前已有许多关于小分子的实验演示，以及模拟材料系统的建议。一些相关方法，如量子计算辅助量子蒙特卡罗方法也已开发出来。不过，目前的器件噪声率太高，无法运行足够深入的电路，以至于无法超越经典电子结构方法。目前还没有证据表明启发式NISQ方法能够扩展到大系统规模，并提供优于经典方法的优势。还有人建议使用模拟量子模拟器来模拟电子结构问题，但据知，这些模拟器尚未得到实验验证。
解决电子结构问题一再被认为是量子计算机最有前途的应用之一；然而，上述讨论凸显了当前量子方法在实用化方面面临的一系列挑战。最值得注意的是，在考虑到通常所做的近似（即包含初始状态准备的成本、使用非最小基集、包括重复进行正确性检查和对一系列参数进行采样）之后，需要大量的逻辑量子比特和总T/Toffoli门。一个主要困难是，与因式分解等问题不同，端到端电子结构问题通常需要解决大量密切相关的问题实例。
对于经典算法和量子算法而言，解决材料的电子结构问题可能比解决分子的电子结构问题更加困难。这主要是由于所考虑的系统规模更大。首创的量子算法可能为有效表示所需的大系统规模提供了一种有前途的方法，而且它们对平面波基础的自然使用非常适合周期性材料系统。
不过，要了解如何将这些算法最好地应用于实际系统，还需要更多的发展。
2、振动结构问题(Vibrational structure problem)
我们寻找哈密顿的能量特征状态（或热态），该哈密顿描述了分子中原子核在其平衡位置附近的振动。该哈密顿方程包含原子核的动能以及原子核在其上运动的有效势能，而有效势能由电子势能面（即以核坐标函数表示的电子能量）决定。
在求解薛定谔方程时，如果将电子和原子核同等对待，那么除了最小的系统外，其他系统的计算成本都会过高。对于可以将电子运动和原子核运动分开（玻恩-奥本海默近似）的系统，我们可以想象原子核在电子势能面(PES)上运动。对于由轻原子组成的分子（可以忽略相对论效应），原子核在其平衡位置附近的振动会对电子能量产生一阶修正，并影响光发射/吸收特性。
对于一个在平衡位置 {RI} 有 G 个经典原子核的系统，其振动哈密顿可以写为：
我们试图制备这种非谐振动哈密顿的特征态（或热态），然后测量这些态的观测值的期望值。我们感兴趣的特性包括：
- PES最小值处的振动能量，它为电子能量提供了一阶修正（用于计算激发能量、确定稳定的分子结构或寻找反应路径和速率）；
- 确定态之间的转变概率和转变偶极矩（用于计算同一电子态振动级之间的红外/拉曼光谱，或不同电子态振动级之间的振动光谱）；
振动态的热态往往比电子态的热态更引人关注：振动能级之间的差异比电子能级之间的差异小，因此，即使在室温下也会有激发振动态出现。这与电子结构问题形成了鲜明对比，在电子结构问题中，许多分子的电子能隙较大，这意味着在室温下，基态通常是人们最感兴趣的状态。
制备所需的特征态或热态可以使用针对电子结构问题所介绍的方法，不过这些方法中的大多数方法在振动问题上的成本尚未确定。例如，可以利用量子相位估算(QPE)来制备能量特征态，给定一个与目标态有足够重叠的态。特征态的制备方法多项式地取决于初始态与期望特征态之间的重叠程度（例如QPE或基于量子奇异值变换QSVT的特征态过滤），或从初始态到期望态绝热路径上的最小能隙。
迄今为止，还没有针对振动结构问题的误差修正资源估算。
有人建议应用变分算法来解决振动结构问题，但似乎不太可能实现足够深的电路来超越经典方法。也有一些模拟量。
然而，由于模拟平台存在退相干性，要将这些模拟扩展到足够大的系统规模似乎很有挑战性。
展望未来，我们还需要做更多的工作，以确定那些对经典模拟具有挑战性，但可能适合量子算法的目标系统。此外，还需要针对振动结构问题所需的精度和振动哈密顿形式进一步优化现有的量子算法。这将使端到端应用的资源估算成为可能——例如估算振动光谱。
模拟核物理和粒子物理似乎本身就是一个量子问题。已经有科学家提议使用量子计算机加速模拟量子场论、核结构、中微子物理和量子引力。在本节中，研究组重点讨论了量子场论和核结构的模拟，因为迄今为止，这些问题在文献中最受关注，也是最接近端到端容错资源估算的问题。
1、量子场论
我们寻求量子场论的静态和动态特性，特别是规范场论和标量场论。规范场论描述物质和/或量规自由度之间的相互作用，可按其对称群分类，如U(1)（描述量子电动力学）、SU(2)（弱相互作用）和SU(3)（量子色动力学）；标量场理论描述标量场之间的相互作用，如希格斯场或ϕ4 理论。
相互作用量子场论通常无法分析求解，扰动理论等技术只能在某些参数区精确求解。例如，量子色动力学(QCD)的低能量——也就是夸克约束和强子形成的机制，无法进行微扰处理。因此，目前在粒子加速器上处理复杂的散射过程时，需要结合第一原理计算和近似现象学方法。
为了从第一性原理出发以数值方法处理量子场论，我们采用了格点场论。然而，格点场论在经典设备上的计算成本很高（这可能是由于哈密尔顿公式中希尔伯特空间的大小，也可能是由于通过蒙特卡罗方法处理的拉格朗日公式中存在的符号问题）。 因此，已经有很多建议使用量子计算机来计算格点场论的静态和动态特性。
将连续场理论离散化到晶格环境中引入了许多细微差别，这些细微差别在经典方法中也存在，但在量子计算中必须重新考虑。例如，费米子场的离散化打破了费米子动力学项的洛伦兹不变性，从而引入了非物理的额外费米子（称为费米子倍增问题）。这个问题可以通过几种既定的方法来缓解，对于量子模拟来说，每种方法都有各自的优点和缺点。此外，还有必要仔细跟踪离散化产生的其他误差，并确保这些误差在缩放和外推到连续极限时消失。
尽管有许多可能的基数可用于规范场论(the gauge degrees)自由度，但目前还不清楚哪种选择是量子模拟的最佳选择。
粒子加速器通常考虑的端到端散射过程过于复杂，无法从第一性原理求解，需要使用一系列近似技术来解决。这些计算通常包括从较简单系统的第一原理格点场论计算中获得的参数，而且通常采用拉格朗日公式，而不是哈密顿公式。这导致对欧几里得时空中的路径积分进行蒙特卡罗采样，应用于动态问题或具有高费米子密度的静态问题受到费米子符号问题的限制。
与量子模拟一样，张量网络方法也不存在符号问题，因此在基于蒙特卡罗的传统方法所无法企及的领域中，也许会引起人们的兴趣。
对于存在符号问题的模拟，经典蒙特卡罗方法在系统规模上的成本是指数级的。此外，据观察，张量网络方法所需的键尺寸随着系统规模的增大而迅速增加，这表明动态问题有可能实现指数级的量化加速。某些场论过程模拟的BQP完备性也加强了这一观点。
目前，利用冷原子或捕获离子等模拟量子模拟器实现LGT简化模型的研究已经取得了重大进展，还有一些研究将变分算法应用于LGT。
关于如何利用量子计算机来补充模拟格点场论的经典方法的研究仍处于初始阶段：虽然量子计算机原则上可以有效地模拟粒子加速器中进行的复杂散射实验，但使用目前已知的技术，这样做所需的资源将是一个天文数字。未来的工作必须确定量子模拟的最佳目标，并努力降低渐近缩放因子和常数前置因子。
特别是量子比特编码（目前对于d空间维度的晶格，每个维度有L个位点，量子比特的缩放为O(Ld)）意味着在进行感兴趣的计算时可能需要大量的逻辑量子比特，可以考虑用L = 10-100来挑战经典方法。
2、核结构问题
核结构可以用壳模型(shell model)来近似描述，壳模型是一种现象学模型，其参数与实验观测结果相匹配。然而，核结构、奇异原子核、精确散射截面或非平衡现象的高精度描述需要第一性原理处理。
除了最简单的原子核之外，从第一性原理描述原子核特性（例如晶格量子色动力学模拟）超出了分析能力和当前计算能力的范围。不过，我们可以整合出短程物理，从而获得描述核子相互作用的有效场理论(EFT)。
手性有效场理论就是一个典型的例子，它描述了核子与虚粒子的相互作用。EFT的参数可以从实验中推断出来（将来也有可能直接从格子QCD计算中确定参数），从而得到描述核子形成和潜在衰变的多体哈密顿。
EFT提供了描述核子如何相互作用的多体哈密顿。寻找该哈密顿的特征态和特征能的经典技术包括坐标空间方法（如量子蒙特卡罗方法）以及投影到基集和使用扰动理论或耦合簇等技术。从这个意义上说，这个问题类似于量子化学中的电子结构问题。 一个常见的问题是制备核子集合的基态，以便计算核结合能并确定特定原子核是否稳定。
模拟还可用于计算散射截面，这些截面可用于分析核-中微子散射、β衰变和核反应的实验。核裂变和核聚变等反应也可以使用显式时间相关方法进行研究，尽管这些方法的计算成本高于静态计算。对核聚变和核裂变反应进行模拟有很多用例，例如可以加深对核天体物理学的理解，因为这些反应通常发生在能量过高或过低的地方，无法在实验中复制。
迄今为止，量子计算方法已经从电子结构问题的量子算法中移植了许多机制。核结构问题可以通过将哈密顿投影到单粒子基础（通常是谐振子特征状态）来解决。在二次量化中，每个单粒子基函数都需要一个量子比特。EFT可以扩展到耦合参数的更高阶；典型的做法是至少保留由先驱引起的3核耦合，高阶项也可以包括在内。
尽管如此，精确比较还取决于其他一些因素（取决于所使用的算法），例如哈密顿项的交换性、系数结构以及问题中的能量标度。
制备能量特征态的量子算法的尺度可以是1/γ（其中γ是初始态与所需特征态的重叠），也可以是绝热路径上的最小间隙大小（见绝热态制备）。 如果我们只对测量态的能量感兴趣，则可以使用量子相位估计算法来获得，该算法也会将系统投影到相应的能量特征态中。这种方法的成本为O(1/γ2)。一旦准备好所需的状态，就可以测量精确度为 ϵ 的观测值，复杂度为 O(1/ϵ2,（直接采样）或O(1/ϵ)（振幅估计）。
上述准备状态的算法（以及在动力学模拟中执行时间演化的相关算法）需要访问哈密顿，这就引入了对哈密顿规范或项数（或两者）的依赖。这些成本在核结构计算中尚未得到阐明。
要使量子算法高效，我们必须能够准备一个与所需状态只有多项式消失重叠的初始状态。这也是困扰电子结构问题量子算法的问题；对于核动力学模拟，也许有必要使用一个足够灵活的基集，以考虑核的位置变化。
EFT 的参数值是通过拟合实验数据获得的，因此可能会在核结构计算中引入系统误差。
经典方法使用与电子结构问题类似的技术，如扰动理论、蒙特卡罗方法或耦合簇；与时间相关的动力学或非平衡现象模拟更具挑战性，也是一个活跃的研究领域。
处理核结构问题的大多数经典方法都会随着系统规模的增大而多项式缩放，但由于使用了近似值（如耦合簇方法中的截断扩展），因此会引入可控误差。要想让量子计算机实现指数级提速，我们需要识别以下系统：
- 经典方法必须指数级地增加资源才能获得准确结果；- 为量子计算准备一个初始状态是有效的，该初始状态与所需状态的重叠度只有多项式衰减。
迄今为止，几乎所有将量子计算应用于核结构问题的工作都集中在变分算法上，目前还没有证据表明，近期的量子设备能够实现足够深度的电路、从而通过这些方法取得超越经典设备的优势。
要确定在量子计算机上解决核结构问题的容错资源，还需要进一步的研究。虽然核结构问题在本质上与量子化学中的电子结构问题相似，但仍有必要将已知算法调整到核环境中，并了解和优化这些算法在经典挑战性问题上的扩展。
核反应动力学模拟似乎是一个特别有趣的目标，但它尚未得到适合量子模拟的彻底重构。
参考链接：
[1]https://www.hpcwire.com/2023/10/05/aws-survey-showcases-quantum-algorithms-and-applications/[2]https://aws.amazon.com/cn/blogs/quantum-computing/constructing-end-to-end-quantum-algorithm/
相关阅读：
迈向容错时代！Quantinuum使用逻辑量子比特实现容错算法
每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！
你可能会错过：|qu|cryovac>